#! /usr/bin/python

import time
now = time.time()

INFINITY = float('inf')
f = open("matrix83.txt", "r")
matrix = []
for l in f:
    matrix.append([int(i) for i in l.split(",")])
N = 80
f.close()

D = [[INFINITY for i in range(N)] for j in range(N)]
D[0][0] = matrix[0][0]	

S = [i for i in range(0, N*N)]

def removeSmallest(S, D):
    mini = INFINITY
    minPos = 0
    for pos in S:
        if D[pos/N][pos%N] < mini: 
	   mini = D[pos/N][pos%N]
	   minPos = pos
    S.remove(minPos)
    return minPos

def getNeighbors(S, pos):
    row = int(pos/N)
    col = int(pos%N)
    up = (row-1)*N + col
    down = (row+1)*N + col
    if col > 0: left = row*N + col - 1
    else: left = -1
    if col < N-1:right = row*N + col + 1
    else: right = -1

    neighbors = []
    if S.count(up) > 0: neighbors.append(up)
    if S.count(down) > 0: neighbors.append(down)
    if S.count(left) > 0: neighbors.append(left)
    if S.count(right) > 0: neighbors.append(right)
    return neighbors
        
while(len(S) != 0):
   pos = removeSmallest(S, D)
   neighbors = getNeighbors(S, pos)
   for i in neighbors:
       new = D[pos/N][pos%N] + matrix[i/N][i%N]
       if D[i/N][i%N] > new: 
	  D[i/N][i%N] = new 

print D[N-1][N-1], time.time()-now
